package com.aaron.leetcode.lc64;

import java.util.Arrays;
import java.util.Random;

/**
 * @author liurong
 * @date 2022/1/21 17:44
 * @version:
 */

/*
    空间换时间
    状态转移方程，递归|迭代
    重叠子问题，备忘录
    自顶向下动态规划解法（递归）
    自底向上的迭代解法 √
 */
public class Solution64_2 {

    static int[][] genMatrix(int m, int n, int randomNumberBound) {
        Random random = new Random();
        int[][] ans = new int[m][n];
        for (int i = 0; i < m; i++) {
            ans[i] = random.ints(n, 1, randomNumberBound).toArray();
        }
        return ans;
    }


    public static void main(String[] args) {

        int[][] grid = genMatrix(4, 5, 10);
        for (int[] row : grid) {
            Arrays.stream(row).forEach(t -> System.out.print(t + " "));
            System.out.println();
        }
        Solution64_1 solution64_1 = new Solution64_1();
        int ans1 = solution64_1.minPathSum(grid);
        System.out.println("ans1:"+ans1);

        Solution64_2 solution64_2 = new Solution64_2();
        int ans2 = solution64_2.minPathSum(grid);
        System.out.println("ans2:"+ans2);

    }

    int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];

        //base case
        dp[0][0] = grid[0][0];

        for (int i = 1; i < m; i++) {
            dp[i][0] = grid[i][0] + dp[i - 1][0];
        }

        for (int j = 1; j < n; j++) {
            dp[0][j] = grid[0][j] + dp[0][j-1];
        }

        //状态转移方程
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(
                        dp[i][j-1],
                        dp[i-1][j]
                ) + grid[i][j];
            }
        }

        return dp[m - 1][n - 1];

    }

}

